package org.laizili.solution.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/tag-validator/">591. 便签验证器</a>
 * <p>
 * tags: 栈; 遍历
 * <p>
 * notes: 注意题目规则描述; 边界条件;
 */
public class Problem591 {
    private static class Solution {
        public boolean isValid(String code) {
            Deque<String> stack = new ArrayDeque<>();
            int i = 0;
            int length = code.length();
            while (i < length) {
                char ch = code.charAt(i);
                if (ch == '<') {
                    if (i + 1 < length) {
                        char nch = code.charAt(i + 1);
                        if (nch == '!') {
                            // cdata
                            if (stack.isEmpty()) {
                                return false;
                            }
                            int ei = i + 9;
                            if (ei < length && "<![CDATA[".equals(code.substring(i, ei))) {
                                ei = code.indexOf("]]>", ei);
                                if (ei == -1) {
                                    return false;
                                }
                                i = ei + 3;
                            } else {
                                // 不是有效的CDATA
                                return false;
                            }
                        } else if (nch == '/') {
                            // close tag
                            if (stack.isEmpty()) {
                                return false;
                            }
                            int ei = code.indexOf('>', i);
                            if (ei == -1) {
                                return false;
                            }
                            String tagName = code.substring(i + 2, ei);
                            if (!isValidTagName(tagName) || !stack.pop().equals(tagName)) {
                                return false;
                            }
                            i = ei + 1;
                            if (stack.isEmpty() && i < length) {
                                return false;
                            }
                        } else {
                            // start tag
                            int ei = code.indexOf('>', i);
                            if (ei == -1) {
                                return false;
                            }
                            String tagName = code.substring(i + 1, ei);
                            if (!isValidTagName(tagName)) {
                                return false;
                            }
                            stack.push(tagName);
                            i = ei + 1;
                        }
                    } else {
                        return false;
                    }

                } else {
                    // tag body
                    if (stack.isEmpty()) {
                        return false;
                    }
                    while (i < length && code.charAt(i) != '<') {
                        i++;
                    }
                }
            }
            return stack.isEmpty();
        }

        private boolean isValidTagName(String tagName) {
            int len = tagName.length();
            boolean matchLengthConstraint = len > 0 && len < 10;
            if (matchLengthConstraint) {
                for (int i = 0; i < len; i++) {
                    char ch = tagName.charAt(i);
                    if (!(ch >= 'A' && ch <= 'Z')) {
                        return false;
                    }
                }
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValid("<DIV>This is the first line <![CDATA[<div>]]></DIV>"));
    }
}

